package com.algorithm.learning.binarysearch;

import java.util.Arrays;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/15 21:42
 **/
public class 在排序数组中查找元素的第一个和最后一个位置 {

    public static void main(String[] args) {
        int[] nums = {1,1, 3, 5, 6, 8,10,20};
        System.out.println(Arrays.toString(searchFirstPosAndLastPos(nums, 1)));
    }

    private static int[] searchFirstPosAndLastPos(int[] nums, int target) {
        int length = nums.length;
        if (length == 0) {
            return new int[]{-1, -1};
        }
        int firstPos = searchFirstPosition(nums, target);
        if (firstPos == -1) {
            return new int[]{-1, -1};
        }
        // 代码能走到这里，说明肯定存在该元素
        int lastPos = searchLastPosition(nums, target);
        return new int[]{firstPos, lastPos};
    }

    private static int searchFirstPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            /*
            要注意这里的判断，一定是if(target > nums[mid]) else, 因为else部分包含了target==nums[mid]，
            如果反过来的话
            if(target < nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
            这里的else就会包含了target==nums[mid]的分支，导致，此时查找的区间是错误的
             */
            if (target > nums[mid]) {
                // 这里要注意，如果目标元素大于mid，那么说明mid和mid左边的一定不存在元素，所以第一次出现的位置肯定不在mid左边
                // 所以这里的区间就是[mid + 1, right]
                left = mid + 1;
            } else {
                // 区间为[left, mid]
                right = mid;
            }
        }
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }

    private static int searchLastPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 这里需要+1的原因还是因为会出现死循环
            // 如果还剩下两个元素，如果left = mid，那么left会一直小于right，导致死循环
            // 所以可以得出一个结论，如果出现left = mid; 和 right = mid - 1;在计算中间数的索引的时候要向上取整。
            int mid = left + (right - left + 1) / 2;
            if (target < nums[mid]) {
                // 这里要注意，如果目标元素小于mid，那么说明mid和mid右边的一定不存在元素，所以最后一次出现的位置肯定不在mid右边
                // 所以这里的区间就是[left, mid - 1]
                right = mid - 1;
            } else {
                // 区间为[mid, right]
                left = mid;
            }
        }
        return left;
    }

}
